Google Maps API Design Evaluation and Latency Budget

Introduction#

We've discussed the design considerations and API model for each functional requirement. In this lesson, we'll cover the approaches for achieving our non-functional requirements and estimate the response time of our Google Maps services.

Non-functional requirements#

Let's discuss how we achieve the non-functional requirements for our APIs one by one.

Availability#

We ensure the availability of our service by replicating our Google Maps services (such as maps, route finder, and places). For example, if a service is not available in one region, the API gateway can route the request to the available replica of this service in another region. Furthermore, if the server is not compatible with the WebSocket while upgrading, we fall back to HTTP/2. It is a trade-off between availability and low latency, but low latency is bearable when it is instead of unavailability of the service.

Accuracy #

The accuracy of the results depends on the accuracy of the client's location, so the GPS should be turned on while using the Google Maps service. It also depends on the backend algorithms (such as Dijkstra's and A* algorithms) of the route-finding service to find the optimal path. Apart from algorithms, technologies like machine learning (ML) play a vital role in finding the best routes. For example, if a frequently used route is suddenly avoided by Google Maps users, the service can intelligently guess that there is a temporary route closure and suggest alternate routes. Another critical factor that improves the accuracy of the service is crowd-sourced traffic information. The ETA is improved by performing analytics on the user's data and finding patterns to detect any anomaly on the routes and, subsequently, adjusting the ETA calculation.

Scalability #

The stateless nature of the HTTP allows our service to scale easily. Because each request is independent, it’s easy for the API gateway to route the incoming requests to any available node. We also make effective use of architectural styles. For instance, we use WebSockets only during the navigation service because we can provide and scale other services conveniently using REST. Moreover, our API has dedicated services working in tandem with each other, still operating independently.

Low latency#

We use the appropriate connection types to obtain low latency for each type of service. For instance, we use WebSocket connections between the client and navigation, which overcomes overheads caused by HTTP/1.1. For the /maps endpoint, we ensure low latency by having regionally distributed CDNs and caching to quickly retrieve the map tiles and the frequently searched places. Furthermore, the neighboring tiles in the vicinity of the user's current location are prefetched, because the user is expected to scroll around the map. We also cache commonly used routes and use them to find new routes. For example, if the path from A to B has been cached, then for the path A->B->C, we use the cached path A->B and only need to find the shortest path from B to C.

Latency budget#

In this section, we'll estimate the response time of our Google Maps API. The response time helps us to measure the performance of our API. We calculate and estimate the size of the request and response for each service. Afterward, we estimate the response time based on the request and response size.

As discussed in the back-of-the-envelope latency calculations, in the case of GET, the average $RTT$ remains the same regardless of the data size (due to the small request size), and the time to download the response varies by $0.4\ ms$ per KB.

Let's start with the maps service.

Maps service#

The maps service uses the GET request to get the links of the map tiles in a response. Let's estimate the request and response size required for the maps service.

• Request size: The estimated request size is 1 KB, including the header and query parameters. The GET method has no body, so the request body size is zero.

• Response size: Assuming that a map tile is roughly 25 KBs in size, the approximate response size for getting map tiles from the maps service, including the response header and body size, is 28 KBs.

We need to calculate latency and processing time to estimate the response time. Our back-of-the-envelope calculations precalculated the average minimum processing time (4 ms) and maximum processing time (69 ms) for interacting with other services to process a request. Remember that we don't assume the size of the request message during the latency and response time calculation of a GET request, because of the small size of the GET request message.

The following calculator calculates the latency and estimates the response time based on our request and response size for the map service.

A summary of the overall response time for the maps service is shown in the illustration below:

Route finder service#

An optimal path includes multiple factors such as ETA, distance, number of turns, and traffic conditions. The route finder service uses a GET request to get a path from the service. The response time for this service always varies depending on various factors, such as the number of steps or stops between the source and destination points.

Let's estimate the request and response size for this service:

• Request size: The estimated request size is 1 KB, including the header and query parameters.

• Response size: Assuming we're traveling from point A to point B without any stop, the approximate response size is 80 KB which includes the size of the header, query parameters, and body.

The following calculator calculates the latency and estimates the response time based on our request and response size for the route finder service.

A summary of the overall response time for the route finder service is shown in the illustration below:

Note: The response time of various requests to interact with maps service is in the ideal range of 0.1–1s, which is adequate according to the low latency requirements.

Navigation service#

The navigation requires a WebSocket connection first, and then the client can exchange data over this connection. An HTTP upgrade connection request to WebSocket happens only once, and it takes a maximum of $275.9\ ms$ to exchange a 1 KB header. The calculation details of the response time to upgrade the connection to WebSockets can be found here.

Let's calculate the response time between clients and the navigation service for sending and receiving events on a WebSocket connection. For example, sending a location from the client and receiving updates related to distance and time from the server side.

Message size#

The estimated size of sending the location to the navigation service is 500 bytes, which includes connection_id, source, and destination. In contrast, the estimated size of receiving the updates related to distance and time takes 700 bytes, which includes connection_id, transport_mode, duration, and distance.

Response time#

We only use the base propagation and download time here, because WebSockets do not follow the request-response model.

A summary of the overall response time for the navigation service is shown in the illustration below:

Note: A latency of 50–100 ms is considered adequate for real-time communication in a persistent connection. The response time for bidirectional communication between the client and the navigation service is ~ $75\ ms$ (an average response time), which is adequate.

Summary#

In this chapter, we learned how to design the API for a route finder and navigation application like Google Maps. We mainly discussed the involved components and their efficient communication in Google Maps. We also discussed how live updates are sent to different clients in real-time. The design decisions made for this problem can also be helpful for similar services, such as Yelp, Uber, Snapchat, and so on.